Взаимное исключение. Семафоры

План лекции

1. Критические секции и взаимное исключение

2. Аппаратные решения: TSL и SWAP

3. Программные решения: алгоритм Петерсона

4. Семафоры Дейкстры

5. Задача «производитель-потребитель»

6. Задача «читатели-писатели»

7. Мониторы Хоара

8. Практические примеры

1. Введение в синхронизацию

В многозадачных ОС несколько процессов одновременно обращаются к общим ресурсам. Это создаёт необходимость в механизмах синхронизации, обеспечивающих корректное выполнение программ.

• Разделяемые ресурсы: память, файлы, устройства I/O
• Параллельный доступ может привести к гонкам данных (race conditions)
• Результат зависит от порядка выполнения процессов
• Требуется координация доступа — взаимное исключение

Критическая секция

Критическая секция — участок кода, в котором процесс обращается к общим ресурсам и который не должен выполняться одновременно несколькими процессами.

Структура процесса:

• Вход в критическую секцию (request entry)
• Критическая секция (critical section)
• Выход из критической секции (exit)
• Остальной код (remainder section)

Условия Бернстайна

Для корректного параллельного выполнения необходимо выполнение трёх условий:

• Взаимное исключение — если процесс в критической секции, другие не могут войти в свои критические секции
• Прогресс — если ни один процесс не в критической секции, выбор процесса для входа не может откладываться бесконечно
• Ограниченное ожидание — существует предел на число раз, когда другие процессы входят в критическую секцию после запроса данного процесса

Пример гонки данных

Два процесса увеличивают общую переменную counter++:

int counter = 0;

// Процесс A                    // Процесс B
reg_A = counter;                reg_B = counter;
reg_A = reg_A + 1;              reg_B = reg_B + 1;
counter = reg_A;                counter = reg_B;

Возможный результат: counter = 1 вместо counter = 2, если переключение контекста произошло между чтением и записью.

2. Аппаратные решения

Подходы, использующие аппаратные инструкции для обеспечения атомарности:

• Отключение прерываний
• Атомарные инструкции процессора:
  • TSL (Test-and-Set Lock)
  • SWAP (обмен значений)
• Аппаратная поддержка гарантирует атомарность на уровне инструкций

Отключение прерываний

Самое простое аппаратное решение — запрет прерываний на время выполнения критической секции.

Команда TSL (Test-and-Set Lock)

Аппаратная команда, которая атомарно читает и устанавливает значение блокировки:

boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = TRUE;
    return rv;
}

Использование для входа в критическую секцию:

while (TestAndSet(&lock))
    ;
// критическая секция
lock = FALSE;

Использование TSL для взаимного исключения

Полное решение с TSL для $n$ процессов:

boolean lock = FALSE;

void enter_region() {
    while (TestAndSet(&lock))
        ;
}

void leave_region() {
    lock = FALSE;
}

• TSL возвращает предыдущее значение и устанавливает TRUE
• Если lock уже TRUE — процесс ждёт (spin lock)
• Если lock был FALSE — процесс входит в секцию

Команда SWAP

void Swap(boolean *a, boolean *b) {
    boolean temp = *a;
    *a = *b;
    *b = temp;
}

boolean lock = FALSE;

void enter_region() {
    boolean key = TRUE;
    do {
        Swap(&key, &lock);
    } while (key == TRUE);
}

void leave_region() {
    lock = FALSE;
}

3. Алгоритм Петерсона

Классический программный алгоритм для двух процессов, обеспечивающий взаимное исключение без специальной аппаратной поддержки.

Идея:

• Каждый процесс объявляет о желании войти в критическую секцию
• Флаг turn указывает, чья очередь
• Процесс ждёт, пока другой находится в критической секции или не его очередь

Реализация алгоритма Петерсона

#define FALSE 0
#define TRUE  1
#define N     2

int turn;
int interested[N];

void enter_region(int process) {
    int other = 1 - process;
    interested[process] = TRUE;
    turn = process;
    while (turn == process && interested[other] == TRUE)
        ;
}

void leave_region(int process) {
    interested[process] = FALSE;
}

Корректность алгоритма Петерсона

Алгоритм удовлетворяет всем трём условиям:

• Взаимное исключение — два процесса не могут одновременно войти: turn допускает только одного
• Прогресс — процесс, не находящийся в критической секции, не мешает другому войти (interested = FALSE)
• Ограниченное ожидание — после выхода процесс уступает очередь (turn = other)

Ограничение: первоначальный вариант работает только для двух процессов. Обобщение — алгоритм пекарни Лампорта.

4. Семафоры Дейкстры

Семафор — синхронизирующий механизм, предложенный Э. Дейкстрой в 1965 году.

Целочисленная переменная с двумя атомарными операциями:

• P (wait, down): уменьшает значение на 1; если результат отрицателен — процесс блокируется
• V (signal, up): увеличивает значение на 1; если есть заблокированные процессы — один разблокируется

P(S):  wait(S > 0);  S = S - 1;
V(S):  S = S + 1;  wakeup_one();

Реализация семафора

typedef struct {
    int value;
    struct process *list;
} semaphore;

void P(semaphore *s) {
    s->value--;
    if (s->value < 0) {
        add this process to s->list;
        block();
    }
}

void V(semaphore *s) {
    s->value++;
    if (s->value <= 0) {
        remove a process P from s->list;
        wakeup(P);
    }
}

Типы семафоров

Использование семафоров для взаимного исключения

semaphore mutex = 1;

// Процесс i
while (TRUE) {
    P(&mutex);
    // критическая секция
    V(&mutex);
    // остальной код
}

• Начальное значение mutex = 1 — один процесс может войти
• Операция P уменьшает до 0 — остальные ждут
• Операция V освобождает и будит ожидающего

5. Задача «производитель-потребитель»

Один или несколько производителей создают данные и помещают их в буфер фиксированного размера. Один или несколько потребителей извлекают данные из буфера.

Условия:

• Производитель ждёт, если буфер полон
• Потребитель ждёт, если буфер пуст
• Доступ к буферу — взаимное исключение

Решение: производитель

#define N 100
semaphore mutex = 1;
semaphore empty = N;
semaphore full  = 0;

void producer() {
    while (TRUE) {
        produce_item();
        P(&empty);
        P(&mutex);
        enter_item();
        V(&mutex);
        V(&full);
    }
}

Решение: потребитель

void consumer() {
    while (TRUE) {
        P(&full);
        P(&mutex);
        remove_item();
        V(&mutex);
        V(&empty);
        consume_item();
    }
}

Почему важен порядок P-операций

Неверный порядок (потребитель):

P(&mutex);    // захватил мьютекс
P(&full);     // буфер пуст → блокировка
              // держит mutex → Producer не войдёт
              // DEADLOCK!

Верный порядок:

P(&full);     // ждёт данные, не держит mutex
P(&mutex);    // захватывает только когда есть что читать

6. Задача «читатели-писатели»

Несколько процессов-читателей и писателей имеют доступ к общей базе данных.

Условия:

• Несколько читателей могут читать одновременно
• Только один писатель может писать в любой момент
• Когда писатель пишет — никто не читает
• Не должно быть бесконечного откладывания

Решение: приоритет читателей

Читатели не ждут, пока есть хотя бы один активный читатель:

semaphore mutex   = 1;
semaphore rw_mutex = 1;
int read_count = 0;

• mutex — защита read_count
• rw_mutex — эксклюзивный доступ для записи (и первого/последнего читателя)
• Первый читатель захватывает rw_mutex, последний — освобождает

Читатель (приоритет читателей)

void reader() {
    while (TRUE) {
        P(&mutex);
        read_count++;
        if (read_count == 1)
            P(&rw_mutex);
        V(&mutex);

        // чтение

        P(&mutex);
        read_count--;
        if (read_count == 0)
            V(&rw_mutex);
        V(&mutex);
    }
}

Писатель (приоритет читателей)

void writer() {
    while (TRUE) {
        P(&rw_mutex);

        // запись

        V(&rw_mutex);
    }
}

Проблема приоритета читателей: писатель может голодать, если читатели приходят непрерывно и read_count никогда не становится 0.

Решение: приоритет писателей

Чтобы избежать голодания писателей, вводится дополнительный семафор w_mutex:

semaphore mutex    = 1;
semaphore rw_mutex = 1;
semaphore w_mutex  = 1;
int read_count  = 0;
int write_count = 0;

• w_mutex — блокирует новых читателей, когда есть ожидающий писатель
• Писатель захватывает mutex через write_count (как читатель — через read_count)

Читатель (приоритет писателей)

void reader() {
    while (TRUE) {
        P(&w_mutex);
        P(&mutex);
        read_count++;
        if (read_count == 1)
            P(&rw_mutex);
        V(&mutex);
        V(&w_mutex);

        // чтение

        P(&mutex);
        read_count--;
        if (read_count == 0)
            V(&rw_mutex);
        V(&mutex);
    }
}

Писатель (приоритет писателей)

void writer() {
    while (TRUE) {
        P(&w_mutex);
        write_count++;
        if (write_count == 1)
            P(&mutex);
        V(&w_mutex);

        P(&rw_mutex);
        // запись
        V(&rw_mutex);

        P(&w_mutex);
        write_count--;
        if (write_count == 0)
            V(&mutex);
        V(&w_mutex);
    }
}

Сравнение подходов «читатели-писатели»

7. Мониторы Хоара

Монитор — высокоуровневый механизм синхронизации, объединяющий данные, операции над ними и синхронизацию в одну структуру.

Характеристики:

• Содержит разделяемые данные
• Определяет операции (процедуры) над этими данными
• Обеспечивает взаимное исключение — только один процесс выполняет процедуру монитора
• Использует переменные условия для синхронизации

Переменные условия в мониторе

Переменные условия (condition variables) используются для блокировки процессов, когда условия не выполнены:

• wait(c) — процесс блокируется на переменной условия c и освобождает монитор
• signal(c) — разбуждает один из процессов, ожидающих на c

Отличие от семафоров:

• Переменные условия не накапливают сигналы
• signal без ожидающих — теряется (без эффекта)
• Взаимное исключение встроено в монитор

Монитор: задача «читатели-писатели»

monitor ReaderWriter {
    int read_count = 0;
    boolean writing = FALSE;
    condition ok_read, ok_write;

    void begin_read() {
        while (writing)
            wait(ok_read);
        read_count++;
        signal(ok_read);
    }

    void end_read() {
        read_count--;
        if (read_count == 0)
            signal(ok_write);
    }
}

Монитор: писатель

void begin_write() {
    while (writing || read_count > 0)
        wait(ok_write);
    writing = TRUE;
}

void end_write() {
    writing = FALSE;
    signal(ok_read);
    signal(ok_write);
}

Преимущества монитора:

• Взаимное исключение — автоматически
• Код проще и менее подвержен ошибкам
• signal будит один процесс; broadcast — все ожидающие

Семафоры vs Мониторы

8. Проблемы синхронизации

Условия Коффмана для deadlock:

• Взаимное исключение
• Удержание и ожидание
• Нет вытеснения
• Циклическое ожидание

Принципы проектирования синхронизации

• Корректность — гарантия отсутствия гонок и ошибок синхронизации
• Эффективность — минимизация времени ожидания и накладных расходов
• Справедливость — предотвращение голодания, равный доступ к ресурсам
• Масштабируемость — работоспособность при увеличении числа процессов

9. Практические примеры

Семафоры и мьютексы в реальных системах:

• System V IPC — semget, semop, semctl
• POSIX — sem_open, sem_wait, sem_post
• pthread — pthread_mutex_lock/unlock
• Linux kernel — mutex, spinlock, rw_semaphore

Семафоры в UNIX (System V)

#include <sys/sem.h>

int semid = semget(IPC_PRIVATE, 1, 0666 | IPC_CREAT);
semctl(semid, 0, SETVAL, 1);

struct sembuf op_p = {0, -1, 0};
struct sembuf op_v = {0,  1, 0};

semop(semid, &op_p, 1);
// критическая секция
semop(semid, &op_v, 1);

Мьютексы в pthread

#include <pthread.h>

pthread_mutex_t mutex;

void init() {
    pthread_mutex_init(&mutex, NULL);
}

void critical_section() {
    pthread_mutex_lock(&mutex);
    // критическая секция
    pthread_mutex_unlock(&mutex);
}

void cleanup() {
    pthread_mutex_destroy(&mutex);
}

Условные переменные в pthread

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  cond  = PTHREAD_COND_INITIALIZER;

// Поток-ожидание
pthread_mutex_lock(&mutex);
while (!condition)
    pthread_cond_wait(&cond, &mutex);
pthread_mutex_unlock(&mutex);

// Поток-уведомитель
pthread_mutex_lock(&mutex);
condition = TRUE;
pthread_cond_signal(&cond);
pthread_mutex_unlock(&mutex);

Иерархия примитивов синхронизации

Перспективы развития

• Безблокирующие алгоритмы (lock-free, wait-free) — повышение производительности
• Адаптивные механизмы — учёт характеристик нагрузки
• Аппаратная поддержка — улучшение эффективности (Intel TSX, ARM LSE)
• Формальная верификация — доказательная корректность алгоритмов

Заключение

Механизмы взаимного исключения и синхронизации — фундамент надёжных многозадачных систем.

Развитие идёт от простых к сложным:

1. Аппаратные инструкции → Семафоры → Мониторы
2. Низкоуровневые примитивы → Высокоуровневые абстракции
3. Ручное управление → Автоматическая синхронизация

Ключевые выводы лекции

Вопросы для самоконтроля

1. Сформулируйте три условия корректного решения задачи о критической секции.
2. Что такое гонка данных? Приведите пример.
3. Как работает команда TSL и почему она обеспечивает атомарность?
4. Объясните алгоритм Петерсона и докажите его корректность.
5. Что такое семафор и какие операции над ним определены?
6. Чем бинарный семафор отличается от считающего?
7. Решите задачу «производитель-потребитель» с помощью семафоров.
8. В чём различие между приоритетом читателей и приоритетом писателей?
9. Какие преимущества monitors дают по сравнению с семафорами?
10. Перечислите условия Коффмана для возникновения взаимной блокировки.

Рекомендуемые ресурсы